﻿//class Solution
//{
//public:
//	vector<vector<int>> threeSum(vector<int>& nums)
//	{
//		vector<vector<int>> ret;
//		sort(nums.begin(), nums.end());
//		int n = nums.size();
//		for (int i = 0; i < n; ) 
//		{
//			if (nums[i] > 0) break; 
//			int left = i + 1, right = n - 1, target = -nums[i];
//			while (left < right)
//			{
//				int sum = nums[left] + nums[right];
//				if (sum > target) right--;
//				else if (sum < target) left++;
//				else
//				{
//					ret.push_back({ nums[i], nums[left], nums[right] });
//					left++, right--;
//					while (left < right && nums[left] == nums[left - 1]) left++;
//					while (left < right && nums[right] == nums[right + 1])
//						right--;
//				}
//			}
//			i++;
//			while (i < n && nums[i] == nums[i - 1]) i++;
//		}
//		return ret;
//	}
//};



//class Solution
//{
//public:
//	void moveZeroes(vector<int>& nums)
//	{
//		for (int cur = 0, dest = -1; cur < nums.size(); cur++)
//			if (nums[cur]) 
//				swap(nums[++dest], nums[cur]);
//	}
//};



//class Solution
//{
//public:
//	void duplicateZeros(vector<int>& arr)
//	{
//		int cur = 0, dest = -1, n = arr.size();
//		while (cur < n)
//		{
//			if (arr[cur]) dest++;
//			else dest += 2;
//			if (dest >= n - 1) break;
//			cur++;
//		}
//		if (dest == n)
//		{
//			arr[n - 1] = 0;
//			cur--; dest -= 2;
//		}
//		while (cur >= 0)
//		{
//			if (arr[cur]) arr[dest--] = arr[cur--];
//			else
//			{
//				arr[dest--] = 0;
//				arr[dest--] = 0;
//				cur--;
//			}
//		}
//	}
//};





//class Solution
//{
//public:
//	int bitSum(int n) 
//		int sum = 0;
//	while (n)
//	{
//		int t = n % 10;
//		sum += t * t;
//		n /= 10;
//	}
//	return sum;
//}
//bool isHappy(int n)
//{
//	int slow = n, fast = bitSum(n);
//	while (slow != fast)
//	{
//		slow = bitSum(slow);
//		fast = bitSum(bitSum(fast));
//	}
//	return slow == 1;
//}
//};




//class Solution {
//public:
//	int maxArea(vector<int>& height) {
//		int n = height.size();
//		int ret = 0;
//		for (int i = 0; i < n; i++) {
//			for (int j = i + 1; j < n; j++) {
//				ret = max(ret, min(height[i], height[j]) * (j - i));
//			}
//		}
//		return ret;
//	}
//};




//class Solution
//{
//public:
//	int maxArea(vector<int>& height)
//	{
//		int left = 0, right = height.size() - 1, ret = 0;
//		while (left < right)
//		{
//			int v = min(height[left], height[right]) * (right - left);
//			ret = max(ret, v);
//			if (height[left] < height[right]) left++;
//			else right--;
//		}
//		return ret;
//	}
//};


//class Solution
//{
//public:
//	int triangleNumber(vector<int>& nums)
//	{
//		sort(nums.begin(), nums.end());
//		int ret = 0, n = nums.size();
//		for (int i = n - 1; i >= 2; i--) 
//		{
//			int left = 0, right = i - 1;
//			while (left < right)
//			{
//				if (nums[left] + nums[right] > nums[i])
//				{
//					ret += right - left;
//					right--;
//				}
//				else
//				{
//					left++;
//				}
//			}
//		}
//		return ret;
//	}
//};



//class Solution
//{
//public:
//	vector<int> twoSum(vector<int>& nums, int target)
//	{
//		int left = 0, right = nums.size() - 1;
//		while (left < right)
//		{
//			int sum = nums[left] + nums[right];
//			if (sum > target) right--;
//			else if (sum < target) left++;
//			else return { nums[left], nums[right] };
//		}
//		return { -4941, -1 };
//	}
//};


class Solution
{
public:
	vector<vector<int>> fourSum(vector<int>& nums, int target)
	{
		vector<vector<int>> ret;
		sort(nums.begin(), nums.end());
		int n = nums.size();
		for (int i = 0; i < n; ) 
		{
			for (int j = i + 1; j < n; )
			{
				int left = j + 1, right = n - 1;
				long long aim = (long long)target - nums[i] - nums[j];
				while (left < right)
				{
					int sum = nums[left] + nums[right];
					if (sum < aim) left++;
					else if (sum > aim) right--;
					else
					{
						ret.push_back({ nums[i], nums[j], nums[left++],
					   nums[right--] });
						// 去重⼀
						while (left < right && nums[left] == nums[left - 1])
							left++;
						while (left < right && nums[right] == nums[right + 1])
							right--;
					}
				}
				// 去重⼆
				j++;
				while (j < n && nums[j] == nums[j - 1]) j++;
			}
			// 去重三
			i++;
			while (i < n && nums[i] == nums[i - 1]) i++;
		}
		return ret;
	}
};